TNotes.leetcode

Appearance

0217. 存在重复元素【简单】

0217. 存在重复元素【简单】 ​

1. 📝 题目描述 ​

给你一个整数数组 nums。

  • 如果任一值在数组中出现至少两次，返回 true
  • 如果数组中每个元素互不相同，返回 false

示例 1：

txt
输入：nums = [1,2,3,1]
输出：true

解释：
元素 1 在下标 0 和 3 出现。

示例 2：

txt
输入：nums = [1,2,3,4]
输出：false

解释：
所有元素都不同。

示例 3：

txt
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

提示：

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

2. 🎯 s.1 - Set ​

js
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) {
  // 利用Set的特性，自动去重
  // 比较原数组长度与Set的大小
  return new Set(nums).size !== nums.length
}
  • 时间复杂度：O(n)，其中 n 是数组长度，需要遍历数组构建 Set
  • 空间复杂度：O(n)，需要额外的 Set 空间存储数组元素

算法思路：

  • 利用 Set 自动去重的特性，比较 Set 大小和原数组长度
  • 如果长度不同，说明存在重复元素

3. 🎯 s.2 - 哈希表记录 ​

js
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) {
  const map = new Map()

  for (let i = 0; i < nums.length; i++) {
    // 如果已存在该元素，说明有重复
    if (map.has(nums[i])) {
      return true
    }
    // 记录当前元素
    map.set(nums[i], true)
  }

  return false
}
  • 时间复杂度：O(n)，其中 n 是数组长度，最坏情况需要遍历完整个数组
  • 空间复杂度：O(n)，需要额外的哈希表空间存储已遍历的元素

算法思路：

  • 使用哈希表记录已经出现过的元素
  • 遍历数组时，如果发现当前元素已在哈希表中，则存在重复

4. 🎯 s.3 - 先排序再比较 ​

js
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) {
  // 先排序
  nums.sort((a, b) => a - b)

  // 相邻元素比较
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) {
      return true
    }
  }

  return false
}
  • 时间复杂度：O(nlog⁡n)，其中 n 是数组长度，主要消耗在排序上
  • 空间复杂度：O(log⁡n)，排序所需的栈空间

算法思路：

  • 先对数组进行排序，使相同元素相邻
  • 然后遍历数组比较相邻元素，如果相等则存在重复

Discussions